一.定义
若能将无向图 画在平面上使得任意两条无重合顶点的边不相交,则称 是平面图。
在平面图中,由边构成的最小区域称为面,包围该面的边数记为该面的度,特殊的,平面图外的区域也为一个面。
比如图一不是平面图,图二因为和图三等价,是平面图。

二.性质
-
平面图的面的度的和等于边数的两倍
显然。 -
欧拉公式:对于联通平面图,, 其中 为点数 , 为边数 , 为面数
证明:
当 ,因为图联通,所以 ,成立。
对 进行数学归纳,若 $e=i $成立,那么对于第 条边
- 两端均为连通块的点,那么便会增加一个面,点数不变。
- 一端为连通块的点,另一端为不在连通块内的点,那么会增加一个点,面数不变。
所以结论成立。
推论:对于任意平面图, , 为平面图的连通块个数
当 ,那么 , 成立。
对 进行数学归纳,若 成立,那么对于第 条边
- 两端的点属于一个连通块,那么便会增加一个面。
- 两端的点不属于一个连通块,那么便会减少一个连通块。
所以结论成立。
3.当 ,平面图的边数不大于 。
一个面至少有三条边,那么平面图的面的度的和至少为 。
又由 得平面图的面的度的和为 。
所以 :
代入欧拉公式得:
三.例题
1.P3209 [HNOI2010]平面图判定